package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2023/12/28 22:08
 */
public class CollectingChocolates {


    /**
     * 实际上我们最大也只需要操作N次，因为N次操作过后所有的类型均已回到原始类型；因此在进行操作又是循环一遍，一定会增加成本；
     * 因此最小的成本一定在N-1次操作之内。所以我们只需要依次计算这N-1次操作的最小成本，再从其中选择最小的即为最终的结果。
     * 注意：依次计算N-1次操作时，我们每次计算需要获取对应下标在X操作之内，其中的最小值。
     * 因此我们需要预先算好每个对应下标在0～N-1次变化，对应的其中最小值是什么。
     * @param nums
     * @param x
     * @return long
     */
    public long minCost(int[] nums, int x) {
        int len = nums.length;
        long[][] dp = new long[len][len];

        // 预先算好每个对应下标在0～N-1次变化，对应的其中最小值是什么。
        for (int i = 0; i < len; i++) {
            dp[i][0] = nums[i];
            for (int j = 1; j < len; j++) {
                dp[i][j] = Math.min(dp[i][j - 1], nums[(i + j) % len]);
            }
        }

        long minCost = Long.MAX_VALUE;
        long tempMinCost;
        for (int i = 0; i < len; i++) {
            tempMinCost = 0;
            for (int j = 0; j < len; j++) {
                tempMinCost += dp[j][i];
            }
            tempMinCost += 1L * i * x;

            if (tempMinCost < minCost) {
                minCost = tempMinCost;
            }
        }
        return minCost;
    }
}
